import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class CombinationSumIII {
    /*
    * 216. 组合总和 III
    * 找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
    * 只使用数字1到9
    * 每个数字 最多使用一次
    * 返回 所有可能的有效组合的列表 。
    * 该列表不能包含相同的组合两次，组合可以以任何顺序返回。
    *
    * 提示:
    * 2 <= k <= 9
    * 1 <= n <= 60
    *
    * */
    public static void main(String[] args){

    }

    // 我的想法：回溯
    public List<List<Integer>> mySolution(int k, int n){
        backtracking(1, n, k);
        return res;
    }
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void backtracking(int start, int sum, int size){
        if(size == 0){
            if(sum == 0)
                res.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = start; i <= 9 - size + 1; i++) {
            if(sum-i < 0)
                break;
            path.add(i);
            backtracking(i+1, sum-i, size-1);
            path.pollLast();
        }
    }
}
